/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓␈↓↓This␈α∪draft␈α∪gives␈α∪insufficient␈α∪mention␈α∪to␈α∪many␈α∪people␈α∪who␈α∪helped␈α∪implement␈α∪LISP␈α∀and␈α∪who
␈↓ ↓H␈↓↓contributed␈αideas.␈α Suggestions␈αfor␈αimprovements␈α
in␈αthat␈αdirections␈αare␈αparticularly␈αwelcome.␈α
 Facts
␈↓ ↓H␈↓↓about the history of FUNARG and uplevel addressing generally are especially needed␈↓.

␈↓ ↓H␈↓α␈↓ ¬?HISTORY OF LISP

␈↓ ↓H␈↓1. Introduction.

␈↓ ↓H␈↓␈↓ α_This␈α∩paper␈α∪concentrates␈α∩on␈α∩the␈α∪development␈α∩of␈α∩the␈α∪basic␈α∩ideas␈α∩and␈α∪distinguishes␈α∩two
␈↓ ↓H␈↓periods␈α-␈αSummer␈α1956␈αthrough␈αSummer␈α1958␈αwhen␈αmost␈αof␈αthe␈αkey␈αideas␈αwere␈αdeveloped␈α(some
␈↓ ↓H␈↓of␈αwhich␈αwere␈αimplemented␈α
in␈αthe␈αFORTRAN␈αbased␈αFLPL),␈α
and␈αFall␈α1958␈αthrough␈α
1962␈αwhen
␈↓ ↓H␈↓the␈α∂programming␈α⊂language␈α∂was␈α∂implemented␈α⊂and␈α∂applied␈α∂to␈α⊂problems␈α∂of␈α⊂artificial␈α∂intelligence.
␈↓ ↓H␈↓The␈α∪scope␈α∩of␈α∪this␈α∪conference␈α∩does␈α∪not␈α∩go␈α∪beyond␈α∪that␈α∩period,␈α∪and␈α∩anyway␈α∪after␈α∪1962,␈α∩the
␈↓ ↓H␈↓development␈α⊃of␈α⊃LISP␈α∩became␈α⊃multi-stranded␈α⊃with␈α⊃different␈α∩ideas␈α⊃being␈α⊃pursued␈α∩in␈α⊃different
␈↓ ↓H␈↓places.

␈↓ ↓H␈↓␈↓ α_As␈αa␈αprogramming␈αlanguage,␈αLISP␈αis␈αcharacterized␈αby␈αthe␈αfollowing␈αideas:␈α computing␈αwith
␈↓ ↓H␈↓symbolic␈α∪expressions␈α∪rather␈α∪than␈α∪numbers,␈α∪representation␈α∪of␈α∪symbolic␈α∪expressions␈α∪and␈α∩other
␈↓ ↓H␈↓information␈α⊃by␈α∩list␈α⊃structure␈α⊃in␈α∩the␈α⊃memory␈α∩of␈α⊃a␈α⊃computer,␈α∩representation␈α⊃of␈α∩information␈α⊃in
␈↓ ↓H␈↓external␈α∞media␈α∞by␈α∞atoms␈α∞and␈α∞lists␈α∞and␈α
secondarily␈α∞by␈α∞S-expressions,␈α∞a␈α∞small␈α∞set␈α∞of␈α∞selector␈α
and
␈↓ ↓H␈↓constructor␈αoperations␈αexpressed␈αas␈αfunctions,␈αcomposition␈αof␈αfunctions␈αas␈αa␈αtool␈αfor␈αforming␈α
more
␈↓ ↓H␈↓complex␈α⊗functions,␈α⊗the␈α⊗use␈α⊗of␈α∃conditional␈α⊗expressions␈α⊗for␈α⊗getting␈α⊗branching␈α⊗into␈α∃function
␈↓ ↓H␈↓definitions,␈α↔the␈α⊗recursive␈α↔use␈α⊗of␈α↔conditional␈α↔expressions␈α⊗as␈α↔a␈α⊗sufficient␈α↔tool␈α↔for␈α⊗building
␈↓ ↓H␈↓computable␈α
functions,␈αthe␈α
use␈αof␈α
λ-expressions␈α
for␈αnaming␈α
functions,␈αthe␈α
representation␈α
of␈αLISP
␈↓ ↓H␈↓programs␈α⊃as␈α⊃LISP␈α⊃data,␈α⊃the␈α⊃conditional␈α⊃expression␈α⊃interpretation␈α⊃of␈α⊃Boolean␈α⊃connectives,␈α⊃the
␈↓ ↓H␈↓LISP␈αfunction␈α␈↓↓eval␈↓␈αthat␈αserves␈αboth␈αas␈αa␈αformal␈αdefinition␈αof␈αthe␈αlanguage␈αand␈αas␈αan␈αinterpreter,
␈↓ ↓H␈↓and␈α∂garbage␈α∞collection␈α∂as␈α∂a␈α∞means␈α∂of␈α∂handling␈α∞the␈α∂erasure␈α∂problem.␈α∞ LISP␈α∂statements␈α∂are␈α∞also
␈↓ ↓H␈↓used as a command language when LISP is used in a time-sharing environment.

␈↓ ↓H␈↓␈↓ α_Some␈αof␈αthese␈αideas␈αwere␈αtaken␈αfrom␈α
other␈αlanguages␈αbut␈αmost␈αwere␈αnew.␈α Towards␈αthe␈α
end
␈↓ ↓H␈↓of␈αthe␈αinitial␈αperiod,␈αit␈αbecame␈αclear␈αthat␈αthis␈αcombination␈αof␈αideas␈αmade␈αan␈αelegant␈αmathematical
␈↓ ↓H␈↓system␈αas␈αwell␈αas␈αa␈αpractical␈αprogramming␈αlanguage.␈α Then␈αmathematical␈αneatness␈αbecame␈αa␈αgoal
␈↓ ↓H␈↓and␈α
led␈α
to␈α
pruning␈α
some␈α
features␈α
from␈α
the␈α
core␈α
of␈α
the␈α
language.␈α
 This␈α
was␈α
partly␈α
motivated␈α
by
␈↓ ↓H␈↓esthetic␈αreasons␈αand␈α
partly␈αby␈αthe␈αbelief␈α
that␈αit␈αwould␈αbe␈α
easier␈αto␈αdevise␈αtechniques␈α
for␈αproving
␈↓ ↓H␈↓programs␈α↔correct␈α↔if␈α↔the␈α⊗semantics␈α↔were␈α↔compact␈α↔and␈α⊗without␈α↔exceptions.␈α↔ The␈α↔results␈α⊗of
␈↓ ↓H␈↓(Cartwright␈α1977),␈αwhich␈αshow␈αthat␈αLISP␈αprograms␈αcan␈αbe␈αinterpreted␈αas␈αsentences␈αof␈αfirst␈αorder
␈↓ ↓H␈↓logic, belatedly confirm the original intuition that logical neatness would pay off.

␈↓ ↓H␈↓2. LISP prehistory - Summer 1956 through Summer 1958.

␈↓ ↓H␈↓␈↓ α_My␈α∞desire␈α∞for␈α∂an␈α∞algebraic␈α∞list␈α∂processing␈α∞language␈α∞for␈α∂artificial␈α∞intelligence␈α∞work␈α∂on␈α∞the
␈↓ ↓H␈↓IBM␈α704␈αcomputer␈αarose␈α
in␈αthe␈αsummer␈αof␈α1956␈α
during␈αthe␈αDartmouth␈αSummer␈αResearch␈α
Project
␈↓ ↓H␈↓on␈αArtificial␈αIntelligence␈αwhich␈αwas␈αthe␈αfirst␈αorganized␈αstudy␈αof␈αAI.␈α During␈αthis␈αmeeting,␈αNewell,
␈↓ ↓H␈↓Shaw␈α
and␈α
Simon␈α
described␈α
IPL␈α
2,␈α
a␈α
list␈α
processing␈α
language␈α
for␈α
Rand␈αCorporation's␈α
JOHNNIAC
␈↓ ↓H␈↓computer␈α
in␈α
which␈αthey␈α
implemented␈α
their␈αLogic␈α
Theorist␈α
program.␈α There␈α
was␈α
little␈αtemptation
␈↓ ↓H␈↓to␈αcopy␈αIPL,␈αbecause␈αits␈αform␈αwas␈αbased␈αon␈αa␈αJOHNNIAC␈αloader␈αthat␈αhappened␈αto␈αbe␈αavailable
␈↓ ↓H␈↓to␈α∞them,␈α∞and␈α∞because␈α∞the␈α∞FORTRAN␈α∞idea␈α∞of␈α∞writing␈α∞programs␈α∞algebraically␈α∞was␈α∂attractive.␈α∞ It
␈↓ ↓H␈↓was␈α
immediately␈α
apparent␈αthat␈α
arbitrary␈α
subexpressions␈α
of␈αsymbolic␈α
expressions␈α
could␈αbe␈α
obtained
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓by␈α
composing␈α
the␈αfunctions␈α
that␈α
extract␈α
immediate␈αsubexpressions,␈α
and␈α
this␈α
seemed␈αreason␈α
enough
␈↓ ↓H␈↓to go to an algebraic language.

␈↓ ↓H␈↓␈↓ α_There␈α
were␈α
two␈α
motivations␈α
for␈α
developing␈α
a␈αlanguage␈α
for␈α
the␈α
IBM␈α
704.␈α
 First,␈α
IBM␈αhad
␈↓ ↓H␈↓generously␈α
undertaken␈αto␈α
establish␈αa␈α
New␈α
England␈αComputation␈α
Center␈αat␈α
M.I.T.,␈αand␈α
Dartmouth
␈↓ ↓H␈↓would␈α∩be␈α∩able␈α∩to␈α∩use␈α∩it.␈α∩ Second,␈α⊃IBM␈α∩was␈α∩undertaking␈α∩to␈α∩develop␈α∩a␈α∩program␈α∩for␈α⊃proving
␈↓ ↓H␈↓theorems␈α∂in␈α⊂plane␈α∂geometry␈α⊂(based␈α∂on␈α⊂an␈α∂idea␈α⊂of␈α∂Marvin␈α⊂Minsky's),␈α∂and␈α⊂I␈α∂was␈α⊂to␈α∂serve␈α⊂as␈α∂a
␈↓ ↓H␈↓consultant␈α
to␈α
that␈αproject.␈α
 At␈α
the␈αtime,␈α
IBM␈α
looked␈αlike␈α
a␈α
good␈αbet␈α
to␈α
pursue␈αartificial␈α
intelligence
␈↓ ↓H␈↓research␈αvigorously,␈αand␈αfurther␈αprojects␈αwere␈αexpected.␈α Moreover,␈αmy␈αown␈αresearch␈αin␈αartificial
␈↓ ↓H␈↓intelligence␈αwas␈α
proceeding␈αalong␈αthe␈α
lines␈αthat␈αled␈α
to␈αthe␈αAdvice␈α
Taker␈αproposal␈αin␈α
1958.␈α This
␈↓ ↓H␈↓project␈α⊃involved␈α∩representing␈α⊃information␈α∩about␈α⊃the␈α⊃world␈α∩by␈α⊃sentences␈α∩in␈α⊃a␈α∩suitable␈α⊃formal
␈↓ ↓H␈↓language␈α
and␈α
deciding␈α
what␈αto␈α
do␈α
by␈α
drawing␈αlogical␈α
consequences.␈α
 Representing␈α
sentences␈αby␈α
list
␈↓ ↓H␈↓structure␈αseemed␈αappropriate␈α-␈αit␈αstill␈αis␈α-␈αand␈αa␈αlist␈αprocessing␈αlanguage␈αalso␈αseemed␈αappropriate
␈↓ ↓H␈↓for programming the operations involved in deduction.

␈↓ ↓H␈↓␈↓ α_This␈α_internal␈α_representation␈α↔of␈α_symbolic␈α_information␈α↔ignores␈α_the␈α_customary␈α↔printed
␈↓ ↓H␈↓notations␈α⊃in␈α⊃favor␈α⊃of␈α⊃simplifying␈α⊃the␈α⊃task␈α⊃of␈α⊃programming␈α⊃the␈α⊃substantive␈α⊃computations,␈α⊃e.g.
␈↓ ↓H␈↓logical␈α
deduction␈α
or␈αalgebraic␈α
simplification,␈α
differentiation␈αor␈α
integration.␈α
 If␈α
standard␈αnotations
␈↓ ↓H␈↓are␈α
to␈αbe␈α
used␈αexternally,␈α
translation␈αprograms␈α
must␈αbe␈α
written.␈α Thus␈α
most␈αprograms␈α
use␈αa␈α
prefix
␈↓ ↓H␈↓notation␈αfor␈αalgebraic␈αexpressions,␈αbecause␈αprograms␈αusually␈αmust␈αdetermine␈αthe␈αoperation␈αbefore
␈↓ ↓H␈↓deciding␈α∂what␈α∞to␈α∂do␈α∞next.␈α∂ In␈α∂this␈α∞LISP␈α∂differs␈α∞from␈α∂almost␈α∞every␈α∂other␈α∂symbolic␈α∞computation
␈↓ ↓H␈↓system.␈α∪ COMIT,␈α∪FORMAC,␈α∪and␈α∪Formula␈α∪Algol␈α∪programs␈α∪all␈α∪express␈α∪the␈α∪computations␈α∩as
␈↓ ↓H␈↓operations␈αon␈αsome␈αapproximation␈αto␈αthe␈αcustomary␈αprinted␈αforms␈αof␈αsymbolic␈αexpressions.␈α This
␈↓ ↓H␈↓may␈α∀account␈α∀for␈α∀LISP's␈α∀success␈α∀in␈α∀competition␈α∀with␈α∀these␈α∀languages,␈α∀especially␈α∀when␈α∀large
␈↓ ↓H␈↓programs have to be written.

␈↓ ↓H␈↓(In␈α∪the␈α∩late␈α∪1950s,␈α∩neat␈α∪output␈α∩and␈α∪convenient␈α∩input␈α∪notation␈α∩was␈α∪not␈α∪generally␈α∩considered
␈↓ ↓H␈↓important.␈α
 Programs␈αto␈α
do␈α
the␈αkind␈α
of␈αinput␈α
and␈α
output␈αcustomary␈α
today␈α
wouldn't␈αeven␈α
fit␈αin␈α
the
␈↓ ↓H␈↓memories available at that time).

␈↓ ↓H␈↓␈↓ α_The␈αfirst␈α
problem␈αwas␈α
how␈αto␈α
do␈αlist␈α
structure␈αin␈α
the␈αIBM␈α
704.␈α This␈α
computer␈αhas␈α
a␈α36␈α
bit
␈↓ ↓H␈↓word,␈α⊃and␈α⊃two␈α⊃15␈α⊃bit␈α⊃parts,␈α⊃called␈α⊃the␈α⊃address␈α⊃and␈α⊃decrement,␈α⊃were␈α⊃distinguished␈α∩by␈α⊃special
␈↓ ↓H␈↓instructions␈α
form␈α
moving␈α∞their␈α
contents␈α
to␈α
and␈α∞from␈α
the␈α
15␈α
bit␈α∞index␈α
registers.␈α
 The␈α∞address␈α
of
␈↓ ↓H␈↓the␈α
machine␈αwas␈α
15␈α
bits,␈αso␈α
it␈αwas␈α
clear␈α
that␈αlist␈α
structure␈αshould␈α
use␈α
15␈αbit␈α
pointers.␈α Therefore,␈α
it
␈↓ ↓H␈↓was␈αnatural␈α
to␈αconsider␈αthe␈α
word␈αas␈αdivided␈α
into␈α4␈αparts,␈α
the␈αaddress␈αpart,␈α
the␈αdecrement␈αpart,␈α
the
␈↓ ↓H␈↓prefix␈αpart␈αand␈α
the␈αtag␈αpart.␈α
 The␈αlast␈αtwo␈α
were␈αthree␈αbits␈α
each␈αand␈αseparated␈α
from␈αeach␈αother␈α
by
␈↓ ↓H␈↓the decrement so that they could not be easily combined into a single six bit part.

␈↓ ↓H␈↓␈↓ α_At␈αthis␈αpoint␈αthere␈αwas␈αsome␈α
indecision␈αabout␈αwhat␈αthe␈αbasic␈αoperators␈αshould␈α
be,␈αbecause
␈↓ ↓H␈↓the␈α∞operation␈α∂of␈α∞extracting␈α∞a␈α∂part␈α∞of␈α∞the␈α∂word␈α∞by␈α∞masking␈α∂was␈α∞considered␈α∞separately␈α∂from␈α∞the
␈↓ ↓H␈↓operation␈αof␈αtaking␈αthe␈αcontents␈αof␈αa␈αword␈αin␈α
memory␈αas␈αa␈αfunction␈αof␈αits␈αaddress.␈α At␈αthe␈αtime,␈α
it
␈↓ ↓H␈↓seemed␈α⊂dubious␈α⊂to␈α⊂regard␈α⊂the␈α⊂latter␈α⊂operation␈α⊂as␈α⊂a␈α⊂function,␈α⊂since␈α⊂its␈α⊂value␈α⊂depended␈α⊂on␈α∂the
␈↓ ↓H␈↓contents␈α⊃of␈α∩memory␈α⊃at␈α∩the␈α⊃time␈α∩the␈α⊃operation␈α⊃was␈α∩performed,␈α⊃so␈α∩it␈α⊃didn't␈α∩act␈α⊃like␈α∩a␈α⊃proper
␈↓ ↓H␈↓mathematical␈α
function.␈α
 However,␈α
the␈α
advantages␈α
of␈αtreating␈α
it␈α
grammatically␈α
as␈α
a␈α
function␈αso␈α
that
␈↓ ↓H␈↓it could be composed were also apparent.

␈↓ ↓H␈↓␈↓ α_Therefore,␈α
the␈αinitially␈α
proposed␈α
set␈αof␈α
functions␈αincluded␈α
␈↓↓cwr␈↓,␈α
standing␈αfor␈α
"Contents␈αof␈α
the
␈↓ ↓H␈↓Word␈α
in␈α∞Register␈α
number"␈α∞and␈α
four␈α∞functions␈α
that␈α∞extracted␈α
the␈α∞parts␈α
of␈α∞the␈α
word␈α∞and␈α
shifted
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓them␈αto␈αa␈αstandard␈αposition␈αat␈αthe␈αright␈αof␈αthe␈αword.␈α An␈αadditional␈αfunction␈αof␈αthree␈αarguments
␈↓ ↓H␈↓that would also extract an arbitrary bit sequence was also proposed.

␈↓ ↓H␈↓␈↓ α_It␈αwas␈αsoon␈αnoticed␈αthat␈αextraction␈α
of␈αa␈αsubexpression␈αinvolved␈αcomposing␈αthe␈αextraction␈α
of
␈↓ ↓H␈↓the␈αaddress␈αpart␈αwith␈α␈↓↓cwr␈↓␈αand␈αthat␈αcontinuing␈αalong␈αthe␈αlist␈αinvolved␈αcomposing␈αthe␈αextraction␈αof
␈↓ ↓H␈↓the␈α∩decrement␈α∩part␈α∪with␈α∩␈↓↓cwr␈↓.␈α∩ Therefore,␈α∪the␈α∩compounds␈α∩␈↓↓car␈↓,␈α∪standing␈α∩for␈α∩"Contents␈α∪of␈α∩the
␈↓ ↓H␈↓Address␈αpart␈αof␈αRegister␈αnumber",␈α
and␈αits␈αanalogs␈α␈↓↓cdr␈↓,␈α␈↓↓cpr␈↓,␈α
and␈α␈↓↓ctr␈↓␈αwere␈αdefined.␈α The␈α
motivation
␈↓ ↓H␈↓for␈α∞implementing␈α
␈↓↓car␈↓␈α∞and␈α
␈↓↓cdr␈↓␈α∞separately␈α
was␈α∞strengthened␈α
by␈α∞the␈α
vulgar␈α∞fact␈α
that␈α∞the␈α∞IBM␈α
704
␈↓ ↓H␈↓had␈α⊃instructions␈α⊃(connected␈α⊂with␈α⊃indexing)␈α⊃that␈α⊂made␈α⊃these␈α⊃operations␈α⊂easy␈α⊃to␈α⊃implement.␈α⊂ A
␈↓ ↓H␈↓construct␈αoperation␈αfor␈αtaking␈αa␈αword␈αoff␈α
the␈αfree␈αstorage␈αlist␈αand␈αstuffing␈αit␈αwith␈α
given␈αcontents
␈↓ ↓H␈↓was␈α
also␈α
obviously␈αrequired.␈α
 At␈α
some␈α
point␈αa␈α
␈↓↓cons(a,d,p,t)␈↓␈α
was␈α
defined,␈αbut␈α
it␈α
was␈α
regarded␈αas␈α
a
␈↓ ↓H␈↓subroutine␈αand␈αnot␈αas␈αa␈αfunction␈αwith␈αa␈αvalue.␈α This␈αwork␈αwas␈αdone␈αat␈αDartmouth,␈αbut␈αnot␈αon␈αa
␈↓ ↓H␈↓computer,␈α
since␈α
the␈α
New␈α
England␈α
Computation␈α
Center␈α
was␈α
not␈α
expected␈α
to␈α
receive␈α
its␈α∞IBM␈α
704
␈↓ ↓H␈↓for another year.

␈↓ ↓H␈↓␈↓ α_In␈α∪connection␈α∀with␈α∪IBM's␈α∀plane␈α∪geometry␈α∀project␈α∪it␈α∀was␈α∪decided␈α∀to␈α∪implement␈α∀a␈α∪list
␈↓ ↓H␈↓processing␈αlanguage␈αwithin␈αFORTRAN,␈αbecause␈αthis␈αseemed␈αto␈αthe␈αthe␈αeasiest␈αway␈αto␈αget␈αstarted,
␈↓ ↓H␈↓and,␈αin␈αthose␈αdays,␈αwriting␈αa␈αcompiler␈αfor␈αa␈αnew␈αlanguage␈αwas␈αbelieved␈αto␈αtake␈αmany␈αman-years.
␈↓ ↓H␈↓This␈α
work␈α
was␈α
undertaken␈α
by␈α
Herbert␈α
Gelernter␈α
and␈α
Carl␈α
Gerberick␈α
at␈α
IBM␈α
and␈α
led␈α
to␈αFLPL,
␈↓ ↓H␈↓standing␈α∞for␈α∞FORTRAN␈α∞List␈α∞Processing␈α∞Language.␈α∞ Gelernter␈α∞and␈α∞Gerberick␈α∞noticed␈α∞that␈α
␈↓↓cons␈↓
␈↓ ↓H␈↓should␈αbe␈αa␈αfunction,␈αnot␈αjust␈αa␈αsubroutine,␈αand␈αthat␈αits␈αvalue␈αshould␈αbe␈αthe␈αlocation␈αof␈αthe␈αword
␈↓ ↓H␈↓that␈α
had␈α
been␈α
stuffed.␈α
 This␈α
permitted␈αnew␈α
expressions␈α
to␈α
be␈α
constructed␈α
out␈αof␈α
subsubexpressions
␈↓ ↓H␈↓by composing occurrences of ␈↓↓cons␈↓.

␈↓ ↓H␈↓␈↓ α_While␈α∞expressions␈α∞could␈α∞be␈α∞handled␈α∞easily␈α∞in␈α∞FLPL,␈α∞and␈α∞it␈α∞was␈α∞used␈α∞successfully␈α∞for␈α∞the
␈↓ ↓H␈↓Geometry␈αprogram,␈αit␈αhad␈αneither␈αconditional␈αexpressions␈αnor␈αrecursion,␈αand␈αerasing␈αlist␈αstructure
␈↓ ↓H␈↓was handled explicitly by the program.

␈↓ ↓H␈↓␈↓ α_I␈α
invented␈α∞conditional␈α
expressions␈α∞in␈α
connection␈α∞with␈α
a␈α
set␈α∞of␈α
chess␈α∞legal␈α
move␈α∞routines␈α
I
␈↓ ↓H␈↓wrote␈αin␈αFORTRAN␈αfor␈αthe␈α
IBM␈α704␈αat␈αM.I.T.␈αduring␈α
1957-58.␈α This␈αprogram␈αdid␈αnot␈α
use␈αlist
␈↓ ↓H␈↓processing.␈α
 The␈αIF␈α
statement␈α
provided␈αin␈α
FORTRAN␈α
1␈αand␈α
FORTRAN␈α
2␈αwas␈α
very␈αawkward␈α
to
␈↓ ↓H␈↓use,␈αand␈αit␈αwas␈αnatural␈αto␈αinvent␈αa␈αfunction␈αXIF(M,N1,N2)␈αwhose␈αvalue␈αwas␈αN1␈αor␈αN2␈αaccording
␈↓ ↓H␈↓to␈αwhether␈αthe␈αexpression␈αM␈αwas␈αzero␈αor␈αnot.␈α The␈αfunction␈αshortened␈αmany␈αprograms␈αand␈αmade
␈↓ ↓H␈↓them␈αeasier␈αto␈αunderstand,␈αbut␈αit␈αhad␈αto␈αbe␈αused␈αsparingly,␈αbecause␈αall␈αthree␈αarguments␈αhad␈αto␈αbe
␈↓ ↓H␈↓evaluated␈α⊂before␈α∂XIF␈α⊂was␈α⊂entered,␈α∂since␈α⊂XIF␈α∂was␈α⊂called␈α⊂as␈α∂an␈α⊂ordinary␈α⊂FORTRAN␈α∂function
␈↓ ↓H␈↓though␈αwritten␈αin␈αmachine␈αlanguage.␈α This␈αled␈α
to␈αthe␈αinvention␈αof␈αthe␈αtrue␈αconditional␈α
expression
␈↓ ↓H␈↓which␈αevaluates␈αonly␈αone␈α
of␈αN1␈αand␈αN2␈αaccording␈α
to␈αwhether␈αM␈αis␈αtrue␈α
or␈αfalse␈αand␈αto␈α
a␈αdesire
␈↓ ↓H␈↓for a programming language that would allow its use.

␈↓ ↓H␈↓␈↓ α_A␈αpaper␈αdefining␈αconditional␈αexpressions␈αand␈αproposing␈αtheir␈αuse␈αin␈αAlgol␈αwas␈αsent␈α
to␈αthe
␈↓ ↓H␈↓␈↓↓Communications␈α
of␈α
the␈α
ACM␈↓␈αbut␈α
was␈α
arbitrarily␈α
demoted␈αto␈α
a␈α
letter␈α
to␈αthe␈α
editor,␈α
because␈α
it␈αwas
␈↓ ↓H␈↓very short.

␈↓ ↓H␈↓␈↓ α_I␈αspent␈αthe␈αsummer␈αof␈α1958␈αat␈αthe␈αIBM␈αInformation␈αResearch␈αDepartment␈αat␈αthe␈αinvitation
␈↓ ↓H␈↓of␈α∞Nathaniel␈α∞Rochester␈α
and␈α∞chose␈α∞differentiating␈α
algebraic␈α∞expressions␈α∞as␈α
a␈α∞sample␈α∞problem.␈α
 It
␈↓ ↓H␈↓led to the following innovations:

␈↓ ↓H␈↓␈↓ α_a.␈α∃Writing␈α∃recursive␈α∃function␈α∃definitions␈α∃using␈α∃conditional␈α∃expressions.␈α∃ The␈α∃idea␈α∀of
␈↓ ↓H␈↓␈↓ εH␈↓ 93


␈↓ ↓H␈↓differentiation␈α⊂is␈α⊂obviously␈α∂recursive,␈α⊂and␈α⊂conditional␈α∂expressions␈α⊂allowed␈α⊂combining␈α⊂the␈α∂cases
␈↓ ↓H␈↓into a single formula.

␈↓ ↓H␈↓␈↓ α_b.␈α∞The␈α∞␈↓↓maplist␈↓␈α∞function␈α∞that␈α∞forms␈α∞a␈α
list␈α∞of␈α∞applications␈α∞of␈α∞a␈α∞functional␈α∞argument␈α∞to␈α
the
␈↓ ↓H␈↓elements␈αof␈αa␈αlist.␈α This␈αwas␈αobviously␈αwanted␈αfor␈αdifferentiating␈αsums␈αof␈αarbitrarily␈αmany␈αterms,
␈↓ ↓H␈↓and␈αwith␈αa␈αslight␈αmodification␈αit␈αcould␈αbe␈αapplied␈αto␈αdifferentiating␈αproducts.␈α (The␈αoriginal␈α
form
␈↓ ↓H␈↓was what is now called ␈↓↓mapcar␈↓).

␈↓ ↓H␈↓␈↓ α_c.␈αTo␈αuse␈αfunctions␈αas␈αarguments,␈αone␈αneeds␈αa␈αnotation␈αfor␈αfunctions,␈αand␈αit␈αseemed␈αnatural
␈↓ ↓H␈↓to␈α∂use␈α∂the␈α∂λ-notation␈α∂of␈α∂Church.␈α∂ I␈α⊂didn't␈α∂understand␈α∂the␈α∂rest␈α∂of␈α∂his␈α∂book␈α∂␈↓↓Calculi␈α⊂of␈α∂Lambda
␈↓ ↓H␈↓↓Conversion␈↓,␈α⊂so␈α∂I␈α⊂wasn't␈α⊂tempted␈α∂to␈α⊂try␈α⊂to␈α∂implement␈α⊂his␈α⊂more␈α∂general␈α⊂mechanism␈α⊂for␈α∂defining
␈↓ ↓H␈↓functions.␈α It␈αused␈αhigher␈αorder␈αfunctionals␈αinstead␈αof␈αusing␈αconditional␈αexpressions.␈α Conditional
␈↓ ↓H␈↓expressions are much more readily implemented on computers.

␈↓ ↓H␈↓␈↓ α_d.␈αThe␈αrecursive␈αdefinition␈αof␈α
differentiation␈αmade␈αno␈αprovision␈αfor␈αerasure␈α
of␈αabandoned
␈↓ ↓H␈↓list␈α⊂structure.␈α∂ No␈α⊂solution␈α∂was␈α⊂apparent␈α∂at␈α⊂the␈α∂time,␈α⊂but␈α∂the␈α⊂idea␈α∂of␈α⊂complicating␈α⊂the␈α∂elegant
␈↓ ↓H␈↓definition␈α
of␈α
differentiation␈α
with␈α
explicit␈α
erasure␈α
was␈α
unattractive.␈α
 Needless␈α
to␈α
say,␈α
the␈α
point␈αof
␈↓ ↓H␈↓the␈αexercise␈αwas␈αnot␈αthe␈αdifferentiation␈αprogram␈αitself,␈αseveral␈αof␈αwhich␈αhad␈αalready␈αbeen␈αwritten,
␈↓ ↓H␈↓but rather clarification of the operations involved in symbolic computation.

␈↓ ↓H␈↓␈↓ α_In␈α∩fact,␈α∩the␈α∩differentiation␈α∩program␈α∩was␈α∩not␈α∩implemented␈α∩that␈α∩summer,␈α∩because␈α⊃FLPL
␈↓ ↓H␈↓allows␈α⊃neither␈α⊃conditional␈α⊃expressions␈α⊂nor␈α⊃recursive␈α⊃use␈α⊃of␈α⊂subroutines.␈α⊃ At␈α⊃this␈α⊃point␈α⊃a␈α⊂new
␈↓ ↓H␈↓language␈α
was␈α
necessary,␈α
since␈α
it␈α
was␈α∞very␈α
difficult␈α
both␈α
technically␈α
and␈α
politically␈α
to␈α∞tinker␈α
with
␈↓ ↓H␈↓Fortran,␈α∞and␈α∞neither␈α∂conditional␈α∞expressions␈α∞nor␈α∞recursion␈α∂could␈α∞be␈α∞implemented␈α∂with␈α∞machine
␈↓ ↓H␈↓language Fortran functions - not even with "functions" that modify the code that calls them.

␈↓ ↓H␈↓2. The implementation of LISP.

␈↓ ↓H␈↓␈↓ α_In␈α∞the␈α∞Fall␈α∂of␈α∞1958,␈α∞I␈α∂became␈α∞Assistant␈α∞Professor␈α∞of␈α∂Communication␈α∞Sciences␈α∞(in␈α∂the␈α∞EE
␈↓ ↓H␈↓Department)␈α∪at␈α∪M.I.T.,␈α∪and␈α∪Marvin␈α∪Minsky␈α∪(then␈α∪an␈α∪assistant␈α∪professor␈α∪in␈α∪the␈α∩Mathemtics
␈↓ ↓H␈↓Department)␈α
and␈α∞I␈α
started␈α
the␈α∞M.I.T.␈α
Artificial␈α
Intelligence␈α∞Project.␈α
 The␈α
Project␈α∞was␈α
supported
␈↓ ↓H␈↓by␈α
the␈α
M.I.T.␈α
Research␈αLaboratory␈α
of␈α
Electronics␈α
which␈α
had␈αa␈α
contract␈α
from␈α
the␈α
armed␈αservices
␈↓ ↓H␈↓that␈αpermitted␈αgreat␈αfreedom␈αto␈αthe␈αDirector,␈αProfessor␈αJerome␈αWiesner,␈αin␈αinitiating␈αnew␈αprojects
␈↓ ↓H␈↓that␈α∂seemed␈α∞to␈α∂him␈α∂of␈α∞scientific␈α∂interest.␈α∂ No␈α∞written␈α∂proposal␈α∂was␈α∞ever␈α∂made.␈α∂ When␈α∞Wiesner
␈↓ ↓H␈↓asked␈αMinsky␈αand␈αme␈αwhat␈αwe␈αneeded␈αfor␈αthe␈αproject,␈αwe␈αasked␈αfor␈αa␈αroom,␈αtwo␈αprogrammers,␈αa
␈↓ ↓H␈↓secretary␈α
and␈αa␈α
keypunch,␈αand␈α
he␈αasked␈α
us␈αto␈α
also␈αundertake␈α
the␈αsupervision␈α
of␈αsome␈α
of␈α
the␈αsix
␈↓ ↓H␈↓mathematics graduate students that R.L.E. had undertaken to support.

␈↓ ↓H␈↓␈↓ α_The␈α⊂implementation␈α⊂of␈α⊃LISP␈α⊂began␈α⊂in␈α⊃Fall␈α⊂1958.␈α⊂ The␈α⊂original␈α⊃idea␈α⊂was␈α⊂to␈α⊃produce␈α⊂a
␈↓ ↓H␈↓compiler,␈α∂but␈α∞this␈α∂was␈α∞considered␈α∂a␈α∞major␈α∂undertaking,␈α∞and␈α∂we␈α∞needed␈α∂some␈α∂experimenting␈α∞in
␈↓ ↓H␈↓order␈αto␈αget␈αgood␈αconventions␈αfor␈αsubroutine␈αlinking,␈αstack␈αhandling␈αand␈αerasure.␈α
 Therefore,␈αwe
␈↓ ↓H␈↓started␈α∞by␈α∞hand-compiling␈α
various␈α∞functions␈α∞into␈α∞assembly␈α
language␈α∞and␈α∞writing␈α∞subroutines␈α
to
␈↓ ↓H␈↓provide␈αa␈αLISP␈α"environment".␈α These␈αincluded␈αprograms␈αto␈αread␈αand␈αprint␈αlist␈αstructure.␈α I␈αcan't
␈↓ ↓H␈↓now␈α∂remember␈α∂whether␈α∂the␈α∂decision␈α∂to␈α∂use␈α∂parenthesized␈α∂list␈α∂notation␈α∂as␈α∂the␈α∂external␈α∂form␈α∞of
␈↓ ↓H␈↓LISP␈α∀data␈α∀was␈α∀made␈α∃then␈α∀or␈α∀whether␈α∀it␈α∀had␈α∃already␈α∀been␈α∀used␈α∀in␈α∀discussing␈α∃the␈α∀paper
␈↓ ↓H␈↓differentiation program.

␈↓ ↓H␈↓␈↓ α_The␈α∩READ␈α∪and␈α∩PRINT␈α∪programs␈α∩induced␈α∩a␈α∪␈↓↓de␈α∩facto␈↓␈α∪standard␈α∩external␈α∪notation␈α∩for
␈↓ ↓H␈↓␈↓ εH␈↓ 94


␈↓ ↓H␈↓symbolic␈α%information,␈α$e.g.␈α%representing␈α$␈↓↓x + 3y + z␈↓␈α%by␈α%(PLUS X (TIMES 3 Y) Z)␈α$and
␈↓ ↓H␈↓␈↓↓(∀x)(P(x)∨Q(x,y))␈↓␈α∪by␈α∪(ALL (X) (OR (P X) (Q X Y))).␈α∩ Any␈α∪other␈α∪notation␈α∪necessarily␈α∩requires
␈↓ ↓H␈↓special␈α⊗programming,␈α⊗because␈α⊗standard␈α↔mathematical␈α⊗notations␈α⊗treat␈α⊗different␈α↔operators␈α⊗in
␈↓ ↓H␈↓syntactically␈α∩different␈α⊃ways.␈α∩ This␈α⊃notation␈α∩came␈α∩to␈α⊃be␈α∩called␈α⊃"Cambridge␈α∩Polish",␈α∩because␈α⊃it
␈↓ ↓H␈↓resembled␈α⊗the␈α∃prefix␈α⊗notation␈α⊗of␈α∃Lukasiewicz,␈α⊗and␈α∃because␈α⊗Quine␈α⊗had␈α∃used␈α⊗also␈α⊗used␈α∃a
␈↓ ↓H␈↓parenthesized prefix notation.

␈↓ ↓H␈↓␈↓ α_The␈α
erasure␈α
problem␈αalso␈α
had␈α
to␈α
be␈αconsidered,␈α
and␈α
it␈α
was␈αclearly␈α
unaesthetic␈α
to␈αuse␈α
explicit
␈↓ ↓H␈↓erasure␈α∞as␈α∞did␈α∞IPL.␈α∞ There␈α∞were␈α∞two␈α∞alternatives.␈α∞ The␈α∞first␈α∞was␈α∞to␈α∞erase␈α∞the␈α∞old␈α∞contents␈α∂of␈α∞a
␈↓ ↓H␈↓program␈α∞variable␈α∞whenever␈α
it␈α∞was␈α∞updated.␈α
 Since␈α∞the␈α∞␈↓↓car␈↓␈α
and␈α∞␈↓↓cdr␈↓␈α∞operations␈α
were␈α∞not␈α∞to␈α
copy
␈↓ ↓H␈↓structure,␈αmerging␈αlist␈αstructure␈αwould␈αoccur,␈αand␈α
so␈αthat␈αerasure␈αwould␈αhave␈αrequired␈αa␈αsystem␈α
of
␈↓ ↓H␈↓reference␈αcounts.␈α Since␈αthere␈αwere␈αonly␈αsix␈αbits␈αleft␈αin␈αa␈αword,␈αand␈αthese␈αwere␈αin␈αseparated␈αparts
␈↓ ↓H␈↓of␈αthe␈αword,␈αreference␈αcounts␈αseemed␈αinfeasible␈αwithout␈αa␈αdrastic␈αchange␈αin␈αthe␈αway␈αlist␈αstructures
␈↓ ↓H␈↓were represented.

␈↓ ↓H␈↓␈↓ α_The␈α∞second␈α∂alternative␈α∞is␈α∂␈↓↓garbage␈α∞collection␈↓␈α∂in␈α∞which␈α∂storage␈α∞is␈α∂abandoned␈α∞until␈α∂the␈α∞free
␈↓ ↓H␈↓storage␈α
list␈α
is␈α
exhausted,␈α
the␈α
storage␈α
accessible␈α
from␈α
program␈α
variables␈α
and␈α
the␈α
stack␈α
is␈α
marked,
␈↓ ↓H␈↓and␈α∂the␈α∂unmarked␈α∂storage␈α∂is␈α∂made␈α∂into␈α∂a␈α∂new␈α∂free␈α∂storage␈α∂list.␈α∂ Once␈α∂we␈α∂decided␈α∂on␈α∞garbage
␈↓ ↓H␈↓collection,␈α∂its␈α∂actual␈α∂implementation␈α∂could␈α∂be␈α∞postponed,␈α∂because␈α∂only␈α∂toy␈α∂examples␈α∂were␈α∞being
␈↓ ↓H␈↓done.␈α (A␈αlist␈αhandling␈αscheme␈αusing␈αreference␈αcounts␈αwas␈αlater␈αused␈αby␈αCollins␈αon␈αa␈α48␈αbit␈αCDC
␈↓ ↓H␈↓computer).

␈↓ ↓H␈↓␈↓ α_At␈α∂that␈α∞time␈α∂it␈α∞was␈α∂also␈α∞decided␈α∂to␈α∞use␈α∂SAVE␈α∞and␈α∂UNSAVE␈α∞routines␈α∂that␈α∞use␈α∂a␈α∞single
␈↓ ↓H␈↓public␈α∪stack␈α∪in␈α∀order␈α∪save␈α∪the␈α∀values␈α∪of␈α∪variables␈α∪and␈α∀subroutine␈α∪return␈α∪addresses␈α∀in␈α∪the
␈↓ ↓H␈↓implementation␈αof␈αrecursive␈α
subroutines.␈α IPL␈αbuilt␈α
stacks␈αas␈αlist␈α
structure␈αand␈αtheir␈α
use␈αhad␈αto␈α
be
␈↓ ↓H␈↓explicitly␈αprogrammed.␈α Another␈αdecision␈αwas␈αto␈αgive␈αup␈αthe␈αprefix␈αand␈αtag␈αparts␈αof␈αthe␈αword,␈αto
␈↓ ↓H␈↓abandon␈α␈↓↓cwr␈↓,␈αand␈αto␈αmake␈α␈↓↓cons␈↓␈αa␈αfunction␈αof␈αtwo␈αarguments.␈α This␈αleft␈αus␈αwith␈αonly␈αa␈αsingle␈αtype
␈↓ ↓H␈↓- the 15 bit address - so that the language didn't require types.

␈↓ ↓H␈↓␈↓ α_These␈α⊃simplifications␈α⊃made␈α∩LISP␈α⊃into␈α⊃a␈α⊃way␈α∩of␈α⊃describing␈α⊃computable␈α∩functions␈α⊃much
␈↓ ↓H␈↓neater␈α∩than␈α⊃the␈α∩Turing␈α⊃machines␈α∩or␈α⊃general␈α∩recursive␈α⊃definitions␈α∩used␈α⊃in␈α∩recursive␈α⊃function
␈↓ ↓H␈↓theory.␈α⊂ The␈α∂fact␈α⊂that␈α∂Turing␈α⊂machines␈α∂constitute␈α⊂an␈α∂awkward␈α⊂programming␈α⊂language␈α∂doesn't
␈↓ ↓H␈↓much␈α⊂bother␈α∂recursive␈α⊂function␈α⊂theorists,␈α∂because␈α⊂they␈α∂almost␈α⊂never␈α⊂have␈α∂any␈α⊂reason␈α⊂to␈α∂write
␈↓ ↓H␈↓particular␈α∂recursive␈α∂definitions,␈α∂since␈α∂the␈α∂theory␈α∂concerns␈α∂recursive␈α∂functions␈α∂in␈α⊂general.␈α∂ They
␈↓ ↓H␈↓often␈αhave␈αreason␈αto␈αprove␈αthat␈αrecursive␈αfunctions␈αwith␈αspecific␈αproperties␈αexist,␈αbut␈αthis␈αcan␈αbe
␈↓ ↓H␈↓done␈α
by␈αan␈α
informal␈α
argument␈αwithout␈α
having␈αto␈α
write␈α
them␈αdown␈α
explicitly.␈α
 In␈αthe␈α
early␈αdays␈α
of
␈↓ ↓H␈↓computing,␈αsome␈αpeople␈α
developed␈αprogramming␈αlanguages␈αbased␈α
on␈αTuring␈αmachines;␈αperhaps␈α
it
␈↓ ↓H␈↓seemed␈α∃more␈α⊗scientific.␈α∃ Anyway,␈α⊗I␈α∃decided␈α⊗to␈α∃write␈α∃a␈α⊗paper␈α∃describing␈α⊗LISP␈α∃both␈α⊗as␈α∃a
␈↓ ↓H␈↓programming␈α
language␈α
and␈αas␈α
a␈α
formalism␈αfor␈α
doing␈α
recursive␈αfunction␈α
theory.␈α
 The␈α
paper␈αwas
␈↓ ↓H␈↓␈↓↓Recursive␈α∪functions␈α∪of␈α∪symbolic␈α∩expressions␈α∪and␈α∪their␈α∪computation␈α∩by␈α∪machine,␈α∪part␈α∪I␈↓␈α∩which
␈↓ ↓H␈↓appeared␈α
in␈α
the␈α
␈↓↓Communications␈α
of␈α∞the␈α
ACM␈↓␈α
in␈α
April␈α
1960.␈α∞ Part␈α
II␈α
was␈α
never␈α
written␈α∞but␈α
was
␈↓ ↓H␈↓intended␈α⊂to␈α⊂contain␈α⊂applications␈α⊂to␈α⊂computing␈α⊂with␈α⊂algebraic␈α⊂expressions.␈α⊂ The␈α⊂paper␈α⊂had␈α⊂no
␈↓ ↓H␈↓influence␈α∂on␈α∞recursive␈α∂function␈α∞theorists,␈α∂because␈α∂it␈α∞didn't␈α∂address␈α∞the␈α∂questions␈α∂that␈α∞interested
␈↓ ↓H␈↓them.

␈↓ ↓H␈↓␈↓ α_One␈α∂way␈α∂to␈α∞show␈α∂that␈α∂LISP␈α∞was␈α∂neater␈α∂than␈α∞Turing␈α∂machines␈α∂was␈α∞to␈α∂write␈α∂a␈α∞universal
␈↓ ↓H␈↓LISP␈αfunction␈αand␈αshow␈αhow␈αmuch␈αbriefer␈αand␈αmore␈αcomprehensible␈αit␈αwas␈αthan␈αthe␈αdescription
␈↓ ↓H␈↓of␈αa␈αuniversal␈α
Turing␈αmachine.␈α This␈αwas␈α
the␈αLISP␈αfunction␈α␈↓↓eval[e,a]␈↓␈α
that␈αcomputes␈αthe␈αvalue␈α
of
␈↓ ↓H␈↓␈↓ εH␈↓ 95


␈↓ ↓H␈↓a␈α
LISP␈α
expression␈α
␈↓↓e␈↓␈α∞-␈α
the␈α
second␈α
argument␈α∞␈↓↓a␈↓␈α
being␈α
a␈α
list␈α∞of␈α
assignments␈α
of␈α
values␈α∞to␈α
variables
␈↓ ↓H␈↓needed␈α⊂to␈α⊃make␈α⊂the␈α⊂recursion␈α⊃work.␈α⊂ Writing␈α⊂␈↓↓eval␈↓␈α⊃required␈α⊂inventing␈α⊂a␈α⊃notation␈α⊂representing
␈↓ ↓H␈↓LISP␈α∂functions␈α∞as␈α∂LISP␈α∞data,␈α∂and␈α∞such␈α∂a␈α∞notation␈α∂was␈α∞devised␈α∂without␈α∞much␈α∂thought␈α∂for␈α∞the
␈↓ ↓H␈↓purposes␈αof␈αthe␈αpaper.␈α Logical␈αcompleteness␈αrequired␈αthat␈αthe␈αnotation␈αused␈αto␈αexpress␈αfunctions
␈↓ ↓H␈↓used␈α∂as␈α∞functional␈α∂arguments␈α∂be␈α∞extended␈α∂to␈α∞provide␈α∂for␈α∂recursive␈α∞functions,␈α∂and␈α∂the␈α∞LABEL
␈↓ ↓H␈↓notation␈α⊂was␈α⊂invented␈α⊂for␈α⊂that␈α⊂purpose.␈α⊂ D.M.R.␈α⊂Park␈α⊂pointed␈α⊂out␈α⊂that␈α⊂LABEL␈α⊂was␈α∂logically
␈↓ ↓H␈↓unnecessary␈α∃since␈α∀the␈α∃result␈α∀could␈α∃be␈α∃achieved␈α∀using␈α∃only␈α∀LAMBDA␈α∃-␈α∀albeit␈α∃in␈α∃a␈α∀more
␈↓ ↓H␈↓complicated␈αway.␈α S.R.␈αRussell,␈α
a␈αprogrammer␈αfor␈αthe␈αproject,␈α
noticed␈αthat␈α␈↓↓eval␈↓␈αcould␈αserve␈α
as␈αan
␈↓ ↓H␈↓interpreter␈αfor␈αLISP,␈αpromptly␈αhand␈αcoded␈αit,␈αand␈αwe␈αnow␈αhad␈αa␈αprogramming␈αlanguage␈αwith␈αan
␈↓ ↓H␈↓interpreter.

␈↓ ↓H␈↓␈↓ α_The␈α∞unexpected␈α∂appearance␈α∞of␈α∞an␈α∂interpreter␈α∞tended␈α∂to␈α∞freeze␈α∞the␈α∂form␈α∞of␈α∂the␈α∞language,
␈↓ ↓H␈↓and␈αsome␈αof␈αthe␈αdecisions␈αmade␈αrather␈αlightheartedly␈αfor␈αthe␈α"Recursive␈αfunctions␈α..."␈α
paper␈αlater
␈↓ ↓H␈↓proved␈αunfortunate.␈α These␈αincluded␈αthe␈αCOND␈αnotation␈αfor␈αconditional␈αexpressions␈αwhich␈αleads
␈↓ ↓H␈↓to␈αan␈αunnecessary␈αdepth␈αof␈αparentheses,␈αand␈αthe␈α
use␈αof␈αthe␈αnumber␈αzero␈αto␈αdenote␈αthe␈α
empty␈αlist
␈↓ ↓H␈↓NIL␈αand␈αthe␈αtruth␈αvalue␈α␈↓αfalse␈↓.␈α Besides␈αencouraging␈αpornographic␈αprogramming,␈αgiving␈αa␈αspecial
␈↓ ↓H␈↓interpretation to the address 0 has caused difficulties in all subsequent implementations.

␈↓ ↓H␈↓3. From LISP I to LISP 1.5.

␈↓ ↓H␈↓␈↓ α_a.␈αProperty␈αlists.␈α The␈αidea␈αof␈αproviding␈αeach␈αatom␈αwith␈αa␈αlist␈αof␈αproperties␈αwas␈αpresent␈αin
␈↓ ↓H␈↓the␈αfirst␈αassembly␈αlanguage␈αimplementation.␈α
 It␈αwas␈αalso␈αone␈αof␈α
the␈αtheoretical␈αideas␈αof␈αthe␈α
Advice
␈↓ ↓H␈↓Taker,␈αalthough␈αthe␈αAdvice␈αTaker␈α(McCarthy␈α1959)␈αwould␈αhave␈αrequired␈αa␈αproperty␈αlist␈αfor␈αany
␈↓ ↓H␈↓expression␈α
for␈α
about␈α
which␈α
information␈α
was␈α∞known␈α
that␈α
did␈α
not␈α
follow␈α
from␈α
its␈α∞structure.␈α
 The
␈↓ ↓H␈↓READ␈α
and␈α
PRINT␈α
programs␈α
required␈α
that␈α
the␈α
print␈α
names␈α
of␈α
atoms␈α
be␈α
accessible,␈α
and␈α
as␈α
soon␈α
as
␈↓ ↓H␈↓function␈αdefinition␈αbecame␈αpossible,␈αit␈αwas␈αnecessary␈αto␈αindicate␈αwhether␈αa␈αfunction␈αwas␈αa␈αSUBR
␈↓ ↓H␈↓in␈α∞machine␈α
code␈α∞or␈α
was␈α∞an␈α
EXPR␈α∞represented␈α
by␈α∞list␈α
structure.␈α∞ Several␈α
functions␈α∞dealing␈α
with
␈↓ ↓H␈↓property lists were also made available for application programs which made heavy use of them.

␈↓ ↓H␈↓␈↓ α_b.␈αInsertion␈α
of␈αelements␈αin␈α
lists␈αand␈α
their␈αdeletion.␈α One␈α
of␈αthe␈α
original␈αadvertised␈αvirtues␈α
of
␈↓ ↓H␈↓list␈α∞processing␈α
for␈α∞AI␈α∞work␈α
was␈α∞the␈α
ability␈α∞to␈α∞insert␈α
and␈α∞delete␈α
elements␈α∞of␈α∞lists.␈α
 Unfortunately,
␈↓ ↓H␈↓this␈α⊃facility␈α⊃coexists␈α⊃uneasily␈α⊂with␈α⊃shared␈α⊃list␈α⊃structure.␈α⊂ Moreover,␈α⊃operations␈α⊃that␈α⊃insert␈α⊂and
␈↓ ↓H␈↓delete␈α⊂don't␈α⊂have␈α⊂a␈α⊂neat␈α⊂representation␈α⊂as␈α∂functions.␈α⊂ LISP␈α⊂contains␈α⊂them␈α⊂in␈α⊂the␈α⊂form␈α⊂of␈α∂the
␈↓ ↓H␈↓␈↓↓rplaca␈↓␈α⊗and␈α↔␈↓↓rplacd␈↓␈α⊗pseudo-functions,␈α⊗but␈α↔programs␈α⊗that␈α⊗use␈α↔them␈α⊗cannot␈α↔be␈α⊗conveniently
␈↓ ↓H␈↓represented␈α∞in␈α∞logic,␈α∞because,␈α∞regarded␈α∞as␈α∞functions,␈α∞they␈α∞don't␈α∞permit␈α∞replacement␈α∞of␈α∞equals␈α
by
␈↓ ↓H␈↓equals.

␈↓ ↓H␈↓␈↓ α_c.␈α
Numbers.␈α
 Many␈α
computations␈α
require␈α
both␈α
numbers␈α
and␈α
symbolic␈αexpressions.␈α
 Numbers
␈↓ ↓H␈↓were␈α⊃implemented␈α⊃in␈α⊃LISP␈α⊃I␈α⊃as␈α⊃lists␈α⊃of␈α∩atoms,␈α⊃and␈α⊃this␈α⊃was␈α⊃useless␈α⊃for␈α⊃all␈α⊃but␈α∩the␈α⊃simplest
␈↓ ↓H␈↓computations.␈α
 A␈α
reasonably␈α
efficient␈α
implementation␈α
of␈α
numbers␈α
as␈α
atoms␈α
in␈α
S-expressions␈α
was
␈↓ ↓H␈↓made␈α
in␈α
LISP␈α
1.5,␈α
but␈α
in␈α
all␈α
the␈α
early␈α
LISPs,␈α
numerical␈α
computations␈α
were␈α
still␈α
10␈α
to␈α∞100␈α
times
␈↓ ↓H␈↓slower␈αthan␈αin␈αFORTRAN.␈α Efficient␈αnumerical␈α
computation␈αrequires␈αsome␈αform␈αof␈αtyping␈αin␈α
the
␈↓ ↓H␈↓source␈α
language␈αand␈α
a␈α
distinction␈αbetween␈α
numbers␈α
treated␈αby␈α
themselves␈α
and␈αas␈α
elements␈α
of␈αS-
␈↓ ↓H␈↓expressions.

␈↓ ↓H␈↓␈↓ α_d.␈α∪Free␈α∪variables.␈α∪ In␈α∩all␈α∪innocence,␈α∪James␈α∪R.␈α∩Slagle␈α∪programmed␈α∪the␈α∪following␈α∩LISP
␈↓ ↓H␈↓function definition and complained when it didn't work right:
␈↓ ↓H␈↓␈↓ εH␈↓ 96


␈↓ ↓H␈↓␈↓ α_␈↓↓testr[x,p,f,u]␈α∀←␈α∀␈↓αif␈↓↓␈α∀p[x]␈α∀␈↓αthen␈↓↓␈α∀f[x]␈α∃␈↓αelse␈↓↓␈α∀␈↓αif␈↓↓␈α∀␈↓αa␈↓↓␈α∀x␈α∀␈↓αthen␈↓↓␈α∀u[]␈α∀␈↓αelse␈↓↓␈α∃testr[␈↓αd␈↓↓␈α∀u,p,f,λ:testr[␈↓αd␈↓↓
␈↓ ↓H␈↓↓u,p,f,u]]␈↓.

␈↓ ↓H␈↓The␈αobject␈αof␈αthe␈αfunction␈αis␈αto␈αfind␈αa␈αsubexpression␈αof␈α␈↓↓x␈↓␈αsatisfying␈α␈↓↓p[x]␈↓␈αand␈αreturn␈α␈↓↓f[x].␈↓␈α If␈αthe
␈↓ ↓H␈↓search␈αis␈αunsuccessful,␈αthen␈αthe␈αcontinuation␈αfunction␈α␈↓↓u[]␈↓␈αof␈αno␈αarguments␈αis␈αto␈αbe␈αcomputed␈αand
␈↓ ↓H␈↓its␈α∂value␈α⊂returned.␈α∂ The␈α∂difficulty␈α⊂was␈α∂that␈α∂when␈α⊂an␈α∂inner␈α∂recursion␈α⊂occurred,␈α∂the␈α∂value␈α⊂of␈α∂␈↓↓u␈↓
␈↓ ↓H␈↓wanted␈α
was␈α
the␈αouter␈α
value,␈α
but␈α
the␈αinner␈α
value␈α
was␈α
actually␈αused.␈α
 In␈α
modern␈αterminology,␈α
lexical
␈↓ ↓H␈↓scoping was wanted, and dynamic scoping was obtained.

␈↓ ↓H␈↓␈↓ α_I␈α
must␈α∞confess␈α
that␈α
I␈α∞regarded␈α
this␈α
difficulty␈α∞as␈α
just␈α
a␈α∞bug␈α
and␈α
expressed␈α∞confidence␈α
that
␈↓ ↓H␈↓Steve␈α
Russell␈α
would␈α
soon␈α
fix␈α∞it.␈α
 He␈α
did␈α
fix␈α
it␈α∞but␈α
by␈α
inventing␈α
the␈α
so-called␈α∞FUNARG␈α
device
␈↓ ↓H␈↓that␈α∞took␈α∞the␈α∞lexical␈α∞environment␈α∞along␈α∞with␈α∞the␈α∞functional␈α∞argument.␈α∞ Similar␈α∞difficulties␈α
later
␈↓ ↓H␈↓showed␈αup␈α
in␈αAlgol␈α60,␈α
and␈αRussell's␈αturned␈α
out␈αto␈αbe␈α
one␈αof␈αthe␈α
more␈αcomprehensive␈αsolutions␈α
to
␈↓ ↓H␈↓the␈α∞problem.␈α
 While␈α∞it␈α∞worked␈α
well␈α∞in␈α∞the␈α
interpreter,␈α∞comprehensiveness␈α∞and␈α
speed␈α∞seem␈α∞to␈α
be
␈↓ ↓H␈↓opposed␈α∂in␈α∞compiled␈α∂code,␈α∂and␈α∞this␈α∂led␈α∞to␈α∂a␈α∂succession␈α∞of␈α∂compromises␈α∞which␈α∂are␈α∂discussed␈α∞in
␈↓ ↓H␈↓Appendix II.

␈↓ ↓H␈↓␈↓ α_e.␈α∂The␈α∂"program␈α∂feature".␈α⊂ Besides␈α∂composition␈α∂of␈α∂functions␈α∂and␈α⊂conditional␈α∂expressions,
␈↓ ↓H␈↓LISP␈αalso␈α
allows␈αsequential␈α
programs␈αwritten␈α
with␈αassignment␈α
statements␈αand␈α
␈↓αgo to␈↓s.␈α Compared
␈↓ ↓H␈↓to␈α∞the␈α
mathematically␈α∞elegant␈α∞recursive␈α
function␈α∞definition␈α∞features,␈α
the␈α∞"program␈α∞feature"␈α
looks
␈↓ ↓H␈↓like␈αa␈αhasty␈αafterthought.␈α This␈αis␈αnot␈αquite␈αcorrect;␈αthe␈αidea␈αof␈αsequential␈αprogram␈αantedates␈αthat
␈↓ ↓H␈↓of␈αrecursive␈α
function␈αdefinition.␈α However,␈α
the␈αnotation␈α
LISP␈αuses␈αfor␈α
PROGs␈αwas␈α
definitely␈αan
␈↓ ↓H␈↓afterthought and is far from optimal.

␈↓ ↓H␈↓␈↓ α_f.␈αOnce␈α
the␈α␈↓↓eval␈↓␈α
interpreter␈αwas␈α
programmed,␈αit␈α
became␈αavailable␈α
to␈αthe␈α
programmer,␈αand␈α
it
␈↓ ↓H␈↓was␈α
especially␈α
easy␈α∞to␈α
use␈α
because␈α
it␈α∞uses␈α
LISP␈α
program␈α
expressed␈α∞as␈α
LISP␈α
data.␈α∞ In␈α
particular,
␈↓ ↓H␈↓␈↓↓eval␈↓␈αmade␈αpossible␈αFEXPRS␈α
and␈αFSUBRS␈αwhich␈αare␈α"functions"␈α
that␈αare␈αnot␈αgiven␈α
their␈αactual
␈↓ ↓H␈↓arguments␈α∩but␈α∩are␈α∩given␈α⊃the␈α∩expressions␈α∩that␈α∩evaluate␈α∩to␈α⊃the␈α∩arguments␈α∩and␈α∩must␈α∩call␈α⊃␈↓↓eval␈↓
␈↓ ↓H␈↓themselves␈αwhen␈αthey␈αwant␈αthe␈αexpressions␈αevaluated.␈α The␈αmain␈αapplication␈αof␈αthis␈αfacility␈αis␈αto
␈↓ ↓H␈↓functions␈αthat␈αdon't␈αalways␈αevaluate␈αall␈αof␈αtheir␈αarguments;␈αthey␈αevaluate␈αsome␈αof␈αthem␈αfirst,␈αand
␈↓ ↓H␈↓then␈α∞decide␈α∞which␈α∞others␈α∞to␈α∞evaluate.␈α∂ This␈α∞facility␈α∞resembles␈α∞Algol's␈α∞␈↓↓call-by-name␈↓␈α∞but␈α∂is␈α∞more
␈↓ ↓H␈↓flexible, because ␈↓↓eval␈↓ is explicitly available.

␈↓ ↓H␈↓␈↓ α_g.␈αSince␈αLISP␈α
works␈αwith␈αlists,␈αit␈α
was␈αalso␈αconvenient␈αto␈α
provide␈αfor␈αfunctions␈αwith␈α
variable
␈↓ ↓H␈↓numbers␈α⊃of␈α⊃arguments␈α⊃by␈α⊃supplying␈α⊃them␈α⊃with␈α⊃a␈α⊃list␈α⊃of␈α⊃arguments␈α⊃rather␈α⊃than␈α∩the␈α⊃separate
␈↓ ↓H␈↓arguments.

␈↓ ↓H␈↓␈↓ α_Unfortunately,␈α∩none␈α∩of␈α∩the␈α∩above␈α∩features␈α∩has␈α∩been␈α∩given␈α∩a␈α∩comprehensive␈α∪and␈α∩clear
␈↓ ↓H␈↓mathematical␈α
semantics␈αin␈α
connection␈αwith␈α
LISP␈α
or␈αany␈α
other␈αprogramming␈α
language.␈α
 The␈αbest
␈↓ ↓H␈↓attempt in connection with LISP is Michael Gordon's (1973), but it is too complicated.

␈↓ ↓H␈↓␈↓ α_As␈αa␈αprogramming␈α
language␈αLISP␈αhas␈α
many␈αlimitations.␈α Some␈αof␈α
the␈αmost␈αevident␈α
in␈αthe
␈↓ ↓H␈↓early␈α
1960s␈αwere␈α
slow␈α
numerical␈αcomputation,␈α
inability␈αto␈α
represent␈α
objects␈αby␈α
blocks␈α
of␈αregisters
␈↓ ↓H␈↓and␈α
garbage␈αcollect␈α
the␈α
blocks,␈αand␈α
lack␈α
of␈αa␈α
good␈α
system␈αfor␈α
input-output␈α
of␈αsymbolic␈α
expressions
␈↓ ↓H␈↓in␈α⊗conventional␈α↔notations.␈α⊗ All␈α↔these␈α⊗problems␈α↔and␈α⊗others␈α⊗were␈α↔to␈α⊗be␈α↔fixed␈α⊗in␈α↔LISP␈α⊗2.
␈↓ ↓H␈↓Unfortunately,␈α_the␈α_LISP␈α_2␈α_project,␈α_undertaken␈α_by␈α_Information␈α_International␈α_and␈α↔System
␈↓ ↓H␈↓Development␈αCorporation␈αproved␈α
too␈αambitious␈αfor␈α
the␈αcomputer␈αthat␈α
had␈αto␈αbe␈α
used␈αand␈αfor␈α
the
␈↓ ↓H␈↓budget␈α⊃of␈α⊃the␈α∩project.␈α⊃ Therefore,␈α⊃we␈α⊃had␈α∩to␈α⊃settle␈α⊃for␈α⊃LISP␈α∩1.5␈α⊃developed␈α⊃at␈α∩M.I.T.␈α⊃which
␈↓ ↓H␈↓corrected only the most glaring deficiencies.
␈↓ ↓H␈↓␈↓ εH␈↓ 97


␈↓ ↓H␈↓␈↓ α_The␈α
existence␈α
of␈αan␈α
interpreter␈α
and␈αthe␈α
absence␈α
of␈αdeclarations␈α
makes␈α
it␈αparticularly␈α
natural
␈↓ ↓H␈↓to␈α
use␈α
LISP␈α
in␈α
a␈α
time-sharing␈α
environment.␈α It␈α
is␈α
convenient␈α
to␈α
define␈α
functions,␈α
test␈α
them,␈αand
␈↓ ↓H␈↓re-edit␈αthem␈αwithout␈αever␈αleaving␈αthe␈αLISP␈αinterpreter.␈α A␈αdemonstration␈αof␈αLISP␈αin␈αa␈αprototype
␈↓ ↓H␈↓time-sharing␈α
environment␈α
on␈α
the␈α
IBM␈α
704␈α∞was␈α
made␈α
in␈α
xxx␈α
1960␈α
(or␈α
1961?).(See␈α∞Appendix␈α
2).
␈↓ ↓H␈↓L.␈αPeter␈αDeutsch␈αimplemented␈αthe␈αfirst␈αinteractive␈αLISP␈αon␈αthe␈αPDP-1␈αcomputer␈αin␈α1963,␈αbut␈αthe
␈↓ ↓H␈↓PDP-1 had too small a memory for serious symbolic computation.

␈↓ ↓H␈↓␈↓ α_The␈αmost␈αimportant␈αimplementations␈αof␈αLISP␈αproved␈αto␈αbe␈αthose␈αfor␈αthe␈αPDP-6␈αcomputer
␈↓ ↓H␈↓and␈α⊗its␈α⊗successor␈α⊗the␈α∃PDP-10␈α⊗made␈α⊗by␈α⊗the␈α∃Digital␈α⊗Equipment␈α⊗Corporation␈α⊗of␈α∃Maynard,
␈↓ ↓H␈↓Massachusetts.␈α∞ In␈α∂fact,␈α∞the␈α∂half␈α∞word␈α∂instructions␈α∞and␈α∂the␈α∞stack␈α∂instructions␈α∞of␈α∂these␈α∞machines
␈↓ ↓H␈↓were␈αdeveloped␈αwith␈αLISP's␈αrequirements␈αin␈αmind.␈α The␈αearly␈αdevelopment␈αof␈αLISP␈αat␈αM.I.T.␈αfor
␈↓ ↓H␈↓this␈α⊃line␈α⊂of␈α⊃machines␈α⊂and␈α⊃its␈α⊂subsequent␈α⊃development␈α⊂of␈α⊃BBN␈α⊂LISP␈α⊃(aka␈α⊃INTERLISP)␈α⊂and
␈↓ ↓H␈↓MACLISP␈α∪also␈α∪contributed␈α∪to␈α∪making␈α∪these␈α∪machines␈α∪the␈α∪machines␈α∪of␈α∪choice␈α∪for␈α∩artificial
␈↓ ↓H␈↓intelligence␈αresearch.␈α The␈αIBM␈α704␈αLISP␈αwas␈αextended␈αto␈αthe␈αIBM␈α7090␈αand␈αlater␈αled␈αto␈αLISPs
␈↓ ↓H␈↓for the IBM 360 and 370.

␈↓ ↓H␈↓␈↓ α_The␈α∂earliest␈α∂publications␈α∂on␈α∂LISP␈α∂were␈α∂in␈α∂the␈α∂Quarterly␈α∂Progress␈α∂Reports␈α∂of␈α∂the␈α∂M.I.T.
␈↓ ↓H␈↓Research␈α⊃Laboratory␈α⊂of␈α⊃Electronics.␈α⊂ (McCarthy␈α⊃1960)␈α⊂was␈α⊃the␈α⊂first␈α⊃journal␈α⊃publication.␈α⊂ The
␈↓ ↓H␈↓␈↓↓LISP␈αProgrammer's␈α
Manual␈↓␈αby␈αPhyllis␈α
Fox␈αwas␈α
published␈αby␈αthe␈α
Research␈αLaboratory␈α
in␈α196x
␈↓ ↓H␈↓and␈αthe␈α␈↓↓LISP␈α1.5␈αProgrammer's␈αManual␈↓␈αby␈αMcCarthy,␈αLevin,␈αet.␈αal.␈α in␈α196x␈αwas␈α
published␈αby
␈↓ ↓H␈↓M.I.T.␈αPress.␈α After␈αthe␈αpublication␈α
of␈α(McCarthy␈αand␈αLevin␈α196x),␈αmany␈α
LISP␈αimplementations
␈↓ ↓H␈↓were␈α∞made␈α∂for␈α∞numerous␈α∞computers.␈α∂ However,␈α∞in␈α∂contrast␈α∞the␈α∞situation␈α∂with␈α∞most␈α∂widely␈α∞used
␈↓ ↓H␈↓programming␈α∞languages,␈α∞no␈α∂organization␈α∞has␈α∞ever␈α∞attempted␈α∂to␈α∞propagate␈α∞LISP,␈α∞and␈α∂there␈α∞has
␈↓ ↓H␈↓never␈α∩been␈α∩an␈α∩attempt␈α∪at␈α∩agreeing␈α∩on␈α∩a␈α∪standardization,␈α∩although␈α∩recently␈α∩A.C.␈α∪Hearn␈α∩has
␈↓ ↓H␈↓developed a "standard LISP" that runs on a number of computers.

␈↓ ↓H␈↓4. Conclusions.

␈↓ ↓H␈↓␈↓ α_LISP␈α∞is␈α∞now␈α
the␈α∞second␈α∞oldest␈α
programming␈α∞language␈α∞(after␈α
FORTRAN␈α∞and␈α∞apart␈α
from
␈↓ ↓H␈↓APT,␈α
which␈α
isn't␈α
used␈α
for␈α
programming␈α
per␈α
se)␈α
in␈α
present␈α
widespread␈α
use.␈α
 It␈α
owes␈α
its␈αlongevity␈α
to
␈↓ ↓H␈↓the␈αfact␈αthat␈αits␈αcore␈α
occupies␈αsome␈αkind␈αof␈αlocal␈α
optimum␈αin␈αthe␈αspace␈αof␈αprogramming␈α
languages
␈↓ ↓H␈↓given␈α⊃that␈α⊃static␈α⊃friction␈α⊃discourages␈α∩purely␈α⊃notational␈α⊃changes.␈α⊃ Recursive␈α⊃use␈α∩of␈α⊃conditional
␈↓ ↓H␈↓expressions,␈α∪representation␈α∀of␈α∪symbolic␈α∪information␈α∀externally␈α∪by␈α∪lists␈α∀and␈α∪internally␈α∀by␈α∪list
␈↓ ↓H␈↓structure,␈α∂and␈α∞representation␈α∂of␈α∂program␈α∞in␈α∂the␈α∞same␈α∂way␈α∂will␈α∞probably␈α∂have␈α∞a␈α∂very␈α∂long␈α∞life.
␈↓ ↓H␈↓LISP␈α~itself␈α~will␈α~probably␈α~become␈α~obsolete␈α~when␈α~someone␈α~succeeds␈α~in␈α~making␈α~a␈α→more
␈↓ ↓H␈↓comprehensive␈α⊃language␈α⊃that␈α⊃dominates␈α⊃LISP␈α⊂practically␈α⊃and␈α⊃also␈α⊃gives␈α⊃a␈α⊃clear␈α⊂mathematical
␈↓ ↓H␈↓semantics to a more comprehensive set of features.

␈↓ ↓H␈↓5. References.
␈↓ ↓H␈↓␈↓ εH␈↓ 98


␈↓ ↓H␈↓APPENDIX I - A MICRO-MANUAL FOR LISP - NOT THE WHOLE TRUTH

␈↓ ↓H␈↓␈↓ α_LISP␈α
data␈αare␈α
symbolic␈α
expressions␈αthat␈α
can␈αbe␈α
either␈α
␈↓↓atoms␈↓␈αor␈α
␈↓↓lists␈↓.␈α ␈↓↓Atoms␈↓␈α
are␈α
strings␈αof
␈↓ ↓H␈↓letters␈α⊃and␈α⊃digits␈α⊃and␈α⊃other␈α⊃characters␈α⊃not␈α⊃otherwise␈α⊃used␈α⊃in␈α⊃LISP.␈α⊃ A␈α⊃list␈α⊃consists␈α⊃of␈α∩a␈α⊃left
␈↓ ↓H␈↓parenthesis␈αfollowed␈α
by␈αzero␈α
or␈αmore␈α
atoms␈αor␈αlists␈α
separated␈αby␈α
spaces␈αand␈α
ending␈αwith␈α
a␈αright
␈↓ ↓H␈↓parenthesis.␈α
 Examples:␈α∞A,␈α
ONION,␈α
(),␈α∞(A),␈α
(A␈α
ONION␈α∞A),␈α
(PLUS␈α
3␈α∞(TIMES␈α
X␈α
PI)␈α∞1),␈α
(CAR
␈↓ ↓H␈↓(QUOTE (A B))).

␈↓ ↓H␈↓␈↓ α_The␈α∂LISP␈α⊂programming␈α∂language␈α⊂is␈α∂defined␈α⊂by␈α∂rules␈α⊂whereby␈α∂certain␈α⊂LISP␈α∂expressions
␈↓ ↓H␈↓have␈αother␈α
LISP␈αexpressions␈αas␈α
␈↓↓values␈↓.␈α The␈αfunction␈α
called␈α␈↓↓value␈↓␈α
that␈αwe␈αwill␈α
use␈αin␈αgiving␈α
these
␈↓ ↓H␈↓rules␈α
is␈α
not␈α
part␈α
of␈α
the␈α
LISP␈α
language␈α
but␈α
rather␈α
part␈α
of␈α
the␈α
informal␈α
mathematical␈α
language␈α
used
␈↓ ↓H␈↓to␈α⊃define␈α⊃LISP.␈α⊃ Likewise,␈α⊃the␈α⊃italic␈α⊃letters␈α⊃␈↓↓e␈↓␈α⊃and␈α⊃␈↓↓a␈↓␈α⊃(sometimes␈α⊃with␈α⊃subscripts)␈α∩denote␈α⊃LISP
␈↓ ↓H␈↓expressions,␈αthe␈αletter␈α␈↓↓v␈↓␈α(usually␈αsubscripted)␈αdenotes␈αan␈αatom␈αserving␈αas␈αa␈αvariable,␈αand␈αthe␈αletter
␈↓ ↓H␈↓␈↓↓f␈↓ stands for a LISP expression serving as a function name.

␈↓ ↓H␈↓1. ␈↓↓value␈↓ (QUOTE ␈↓↓e)␈↓ = e.  Thus the value of (QUOTE A) is A.

␈↓ ↓H␈↓2.␈α⊃␈↓↓value␈↓␈α⊃(CAR␈α⊃␈↓↓e),␈↓␈α⊃where␈α⊃␈↓↓value␈α⊃e␈↓␈α⊃is␈α⊂a␈α⊃non-empty␈α⊃list,␈α⊃is␈α⊃the␈α⊃first␈α⊃element␈α⊃of␈α⊃␈↓↓value e.␈↓␈α⊂ Thus
␈↓ ↓H␈↓␈↓↓value␈↓ (CAR (QUOTE (A B C))) = A.

␈↓ ↓H␈↓3.␈α∞␈↓↓value␈↓␈α∞(CDR␈α∞e),␈α∞where␈α∞␈↓↓value␈↓␈α∞␈↓↓e␈↓␈α∞is␈α∞a␈α
non-empty␈α∞list,␈α∞is␈α∞the␈α∞the␈α∞list␈α∞that␈α∞remains␈α∞when␈α∞the␈α
first
␈↓ ↓H␈↓element of ␈↓↓value e␈↓ is deleted.  Thus ␈↓↓value␈↓ (CDR (QUOTE (A B C))) = (B C).

␈↓ ↓H␈↓4.␈α
␈↓↓value␈↓␈α
(CONS␈α
␈↓↓e1␈↓␈α
␈↓↓e2),␈↓␈α
is␈α
the␈α
list␈α
that␈α
results␈α
from␈α
prefixing␈α
␈↓↓value e1␈↓␈α
onto␈α
the␈α
list␈α
␈↓↓value e2.␈↓␈α
 Thus
␈↓ ↓H␈↓␈↓↓value␈↓ (CONS (QUOTE A) (QUOTE (B C))) = (A B C).

␈↓ ↓H␈↓5.␈α∩␈↓↓value␈↓␈α∩(EQUAL␈α∩␈↓↓e1␈↓␈α⊃␈↓↓e2)␈↓␈α∩is␈α∩T␈α∩if␈α∩␈↓↓value␈↓␈α⊃␈↓↓e1␈↓␈α∩=␈α∩␈↓↓value␈↓␈α∩␈↓↓e2.␈↓␈α⊃ Otherwise,␈α∩its␈α∩value␈α∩is␈α∩NIL.␈α⊃ Thus
␈↓ ↓H␈↓␈↓↓value␈↓ (EQUAL (CAR (QUOTE (A B))) (QUOTE A)) = T.

␈↓ ↓H␈↓6. ␈↓↓value␈↓ (ATOM ␈↓↓e)␈↓ = T if ␈↓↓value␈↓ ␈↓↓e␈↓ is an atom; otherwise its value is NIL.

␈↓ ↓H␈↓7.␈α
␈↓↓value␈↓␈α(COND(␈↓↓p␈↓β1␈↓↓␈α
e␈↓β1␈↓↓)␈α
...␈α(p␈↓βn␈↓↓␈α
e␈↓βn␈↓↓))␈α
=␈αvalue␈α
e␈↓βi␈↓,␈αwhere␈α
␈↓↓p␈↓βi␈↓␈α
is␈αthe␈α
the␈α
first␈αof␈α
the␈α
␈↓↓p␈↓'s␈αwhose␈α
value␈αis␈α
not
␈↓ ↓H␈↓NIL.  Thus

␈↓ ↓H␈↓␈↓↓value␈↓ (COND ((ATOM (QUOTE A)) (QUOTE B)) ((QUOTE T) (QUOTE C))) = B.

␈↓ ↓H␈↓8. An atom ␈↓↓v,␈↓ regarded as a variable, may have a value.

␈↓ ↓H␈↓9.␈α
␈↓↓value␈↓␈α
((LAMBDA␈α
(␈↓↓v␈↓β1␈↓↓␈α
...␈α
v␈↓βn␈↓↓)␈α
e)␈α
e␈↓β1␈↓↓␈α
...␈α
e␈↓βn␈↓↓)␈↓␈α
is␈α
the␈α
same␈α
as␈α
␈↓↓value e␈↓␈α
but␈α
in␈α
an␈α
environment␈α
in␈α
which
␈↓ ↓H␈↓the␈α∞variables␈α∞␈↓↓v␈↓β1␈↓↓ ... v␈↓βn␈↓↓␈↓␈α∞take␈α∞the␈α∞values␈α∂of␈α∞the␈α∞expressions␈α∞␈↓↓e␈↓β1␈↓↓ ... e␈↓βn␈↓↓␈↓␈α∞in␈α∞the␈α∂original␈α∞environment.
␈↓ ↓H␈↓Thus

␈↓ ↓H␈↓␈↓↓value␈↓␈α((LAMBDA␈α(X␈α
Y)␈α(CONS␈α(CAR␈α
X)␈αY))␈α(QUOTE␈α
(A␈αB))␈α(CDR␈α
(QUOTE␈α(C␈αD))))␈α
=␈α(A
␈↓ ↓H␈↓D).

␈↓ ↓H␈↓10.␈α∞Here's␈α∞the␈α∞hard␈α∞one.␈α∞ ␈↓↓value␈↓␈α
((LABEL␈α∞␈↓↓f␈↓␈α∞(LAMBDA␈α∞␈↓↓(v␈↓β1␈↓↓␈α∞...␈α∞v␈↓βn␈↓↓)␈α
e))␈α∞e␈↓β1␈↓↓␈α∞...␈α∞e␈↓βn␈↓↓)␈↓␈α∞is␈α∞the␈α∞same␈α
as
␈↓ ↓H␈↓␈↓↓value␈↓␈α
((LAMBDA␈α
(␈↓↓v␈↓β1␈↓↓␈α
...␈α
v␈↓βn␈↓↓)␈α
e)␈α
e␈↓β1␈↓↓␈α
...␈α
e␈↓βn␈↓↓)␈↓␈α
with␈α
the␈α
additional␈α
rule␈α
that␈α
whenever␈α
␈↓↓(f a␈↓β1␈↓↓ ... a␈↓βn␈↓↓)␈↓␈α
must
␈↓ ↓H␈↓be␈α
evaluated,␈α␈↓↓f␈↓␈α
is␈αreplaced␈α
by␈α(LABEL ␈↓↓f␈↓ (LAMBDA (␈↓↓v␈↓β1␈↓↓ ... v␈↓βn␈↓↓)␈α
e))␈↓.␈α Lists␈α
beginning␈αwith␈α
LABEL
␈↓ ↓H␈↓define functions recursively.
␈↓ ↓H␈↓␈↓ εH␈↓ 99


␈↓ ↓H␈↓␈↓ α_This is the core of LISP, and here are more examples:

␈↓ ↓H␈↓␈↓↓value␈↓␈α(CAR␈αX)␈α=␈α(A␈αB)␈αif␈α␈↓↓value␈↓␈αX␈α=␈α((A␈αB)␈αC),␈αand␈α␈↓↓value␈↓␈α((LABEL␈αFF␈α(LAMBDA␈α(X)␈α(COND
␈↓ ↓H␈↓((ATOM␈αX)␈αX)␈α((QUOTE␈αT)␈α(FF␈α(CAR␈αX))))))␈α(QUOTE␈α((A␈αB)␈αC)))␈α=␈αA.␈α Thus␈α((LABEL␈αFF
␈↓ ↓H␈↓(LAMBDA␈α(X)␈α(COND␈α((ATOM␈αX)␈αX)␈α((QUOTE␈αT)␈α(FF␈α(CAR␈αX)))))),␈αis␈αthe␈αLISP␈αname␈αof␈αa
␈↓ ↓H␈↓function␈α⊂␈↓↓ff␈↓␈α⊂such␈α⊂that␈α⊂␈↓↓ff e␈↓␈α⊂is␈α∂the␈α⊂first␈α⊂atom␈α⊂in␈α⊂the␈α⊂written␈α⊂form␈α∂of␈α⊂␈↓↓e.␈↓␈α⊂Note␈α⊂that␈α⊂the␈α⊂list␈α⊂␈↓↓ff␈↓␈α∂is
␈↓ ↓H␈↓substituted for the atom FF twice.

␈↓ ↓H␈↓Difficult mathematical type exercise: Find a list e such that ␈↓↓value e = e.␈↓

␈↓ ↓H␈↓␈↓αAbbreviations␈↓

␈↓ ↓H␈↓␈↓ α_The above LISP needs some abbreviations for practical use.

␈↓ ↓H␈↓1.␈α∞The␈α∞variables␈α∞T␈α∞and␈α∞NIL␈α∞are␈α∞permanently␈α
assigned␈α∞the␈α∞values␈α∞T␈α∞and␈α∞NIL,␈α∞and␈α∞NIL␈α∞is␈α
the
␈↓ ↓H␈↓name of the null list ().

␈↓ ↓H␈↓2.␈αSo␈αas␈αnot␈αto␈αdescribe␈αa␈αLISP␈αfunction␈αeach␈αtime␈αit␈αis␈αused,␈αwe␈αdefine␈αit␈αpermanently␈αby␈αtyping
␈↓ ↓H␈↓(DEFUN␈α␈↓↓f␈α(v␈↓β1␈↓↓␈α...␈αv␈↓βn␈↓↓)␈αe)␈↓.␈α Thereafter␈α␈↓↓(f␈αe␈↓β1␈↓↓␈α...␈αe␈↓βn␈↓↓)␈↓␈αis␈αevaluated␈αby␈αevaluating␈α␈↓↓e␈↓␈αwith␈αthe␈αvariables
␈↓ ↓H␈↓␈↓↓v␈↓β1␈↓↓, ... ,v␈↓βn␈↓↓␈↓␈αtaking␈αthe␈α
values␈α␈↓↓value e␈↓β1␈↓↓, ... ,value e␈↓βn␈↓↓␈↓␈αrespectively.␈α
 Thus,␈αafter␈αwe␈αdefine␈α
(DEFUN
␈↓ ↓H␈↓FF␈α
(X)␈α
(COND␈α((ATOM␈α
X)␈α
X)␈α(T␈α
(FF␈α
(CAR␈α
X))))),␈αtyping␈α
 (FF␈α
(QUOTE␈α((A␈α
B)␈α
C))),␈α
gets␈αA
␈↓ ↓H␈↓from LISP.

␈↓ ↓H␈↓3. We have the permanent function definitions

␈↓ ↓H␈↓(DEFUN NULL (X) (EQUAL X NIL)) and

␈↓ ↓H␈↓(DEFUN CADR (X) (CAR (CDR X))),

␈↓ ↓H␈↓and similarly for arbitrary combinations of A and D.

␈↓ ↓H␈↓4. (LIST ␈↓↓e␈↓β1␈↓↓ ... e␈↓βn␈↓↓␈↓) is defined for each ␈↓↓n␈↓ to be (CONS ␈↓↓e␈↓␈↓β1␈↓ (CONS ... (CONS ␈↓↓e␈↓␈↓βn␈↓ NIL))).

␈↓ ↓H␈↓5.␈α(AND␈α␈↓↓p␈↓␈α␈↓↓q)␈↓␈αabbreviates␈α(COND␈α(␈↓↓p␈↓␈α␈↓↓q)␈↓␈α(T␈αNIL)).␈α ANDs␈αwith␈αmore␈αterms␈αare␈αdefined␈αsimilarly,
␈↓ ↓H␈↓and␈α∃the␈α⊗propositional␈α∃connectives␈α⊗OR␈α∃and␈α⊗NOT␈α∃are␈α⊗used␈α∃in␈α⊗abbreviating␈α∃corresponding
␈↓ ↓H␈↓conditional expressions.

␈↓ ↓H␈↓␈↓ α_Here are more examples of LISP function definitions:

␈↓ ↓H␈↓(DEFUN␈αALT␈α(X)␈α(COND␈α((OR␈α(NULL␈αX)␈α(NULL␈α(CDR␈αX)))␈αX)␈α(T␈α(CONS␈α(CAR␈αX)␈α(ALT
␈↓ ↓H␈↓(CDDR X))))))

␈↓ ↓H␈↓defines␈α∂a␈α∂function␈α∂that␈α∂gives␈α∂alternate␈α∂elements␈α∂of␈α∂a␈α∂list␈α∂starting␈α∂with␈α∂the␈α∂first␈α⊂element.␈α∂ Thus
␈↓ ↓H␈↓(ALT (QUOTE (A B C D E))) = (A C E).

␈↓ ↓H␈↓(DEFUN␈α
SUBST␈α(X␈α
Y␈αZ)␈α
(COND␈α((ATOM␈α
Z)␈α(COND␈α
((EQUAL␈αZ␈α
Y)␈αX)␈α
(T␈αZ)))␈α
(T␈α(CONS
␈↓ ↓H␈↓(SUBST X Y (CAR Z)) (SUBST X Y (CDR Z)))))),

␈↓ ↓H␈↓where Y is an atom, gives the result of substituting X for Y in Z.  Thus
␈↓ ↓H␈↓␈↓ εH␈↓ *10


␈↓ ↓H␈↓(SUBST␈α(QUOTE␈α(PLUS␈α
X␈αY))␈α(QUOTE␈α
V)␈α(QUOTE␈α(TIMES␈αX␈α
V)))␈α=␈α(TIMES␈α
X␈α(PLUS
␈↓ ↓H␈↓X Y)).

␈↓ ↓H␈↓␈↓ α_You␈α⊃may␈α⊃now␈α⊃program␈α⊂in␈α⊃LISP.␈α⊃ Call␈α⊃LISP␈α⊂on␈α⊃a␈α⊃time-sharing␈α⊃computer,␈α⊃define␈α⊂some
␈↓ ↓H␈↓functions, type in a LISP expression, and LISP will output its value on your terminal.
␈↓ ↓H␈↓␈↓ εH␈↓ *11


␈↓ ↓H␈↓APPENDIX II - HISTORY OF SCOPING IN LISP

␈↓ ↓H␈↓␈↓ α_ APPENDIX III - Humorous Anecdote

␈↓ ↓H␈↓␈↓ α_The␈αfirst␈αon-line␈αdemonstration␈αof␈αLISP␈αwas␈αalso␈αthe␈αfirst␈αdemonstration␈αof␈αa␈αprecursor␈αof
␈↓ ↓H␈↓time-sharing␈α∞that␈α∞we␈α∞called␈α∞"time-stealing".␈α∞ The␈α
audience␈α∞comprised␈α∞the␈α∞participants␈α∞in␈α∞one␈α
of
␈↓ ↓H␈↓M.I.T.'s␈αIndustrial␈αLiaison␈αSymposia␈αon␈αwhom␈αit␈αwas␈αimportant␈αto␈αmake␈αa␈αgood␈αimpression␈αsince
␈↓ ↓H␈↓they␈α∂contribute␈α∂money.␈α∂ A␈α∂Flexowriter␈α∂had␈α∂been␈α∂connected␈α∂to␈α∂the␈α∂IBM␈α∂704␈α∂and␈α∂the␈α∞operating
␈↓ ↓H␈↓system␈α∩modified␈α∩so␈α∩that␈α∩it␈α∩collected␈α∩characters␈α∩from␈α∩the␈α∩Flexowriter␈α∩in␈α∩a␈α∩buffer␈α∩when␈α⊃their
␈↓ ↓H␈↓presence␈αwas␈αsignalled␈αby␈αan␈αinterrupt.␈α At␈αthe␈αend␈αof␈αeach␈αjob␈αin␈αthe␈αtape-to-tape␈αbatch␈αqueue,
␈↓ ↓H␈↓the␈α
operating␈α
system␈αwould␈α
check␈α
to␈αsee␈α
if␈α
a␈α
full␈αline␈α
was␈α
ready␈αfor␈α
processing␈α
by␈αthe␈α
time-stealing
␈↓ ↓H␈↓program.

␈↓ ↓H␈↓␈↓ α_The␈αdemonstration␈αwas␈αalso␈α
one␈αof␈αthe␈αfirst␈α
to␈αuse␈αclosed␈αcircuit␈α
TV␈αin␈αorder␈αto␈α
spare␈αthe
␈↓ ↓H␈↓spectators␈α
the␈α
museum␈α
feet␈α
consequent␈α
on␈α
crowding␈α
around␈α
a␈α
terminal␈α
waiting␈α
for␈α∞something␈α
to
␈↓ ↓H␈↓happen.␈α∞ Thus␈α
they␈α∞were␈α
on␈α∞the␈α
fourth␈α∞floor␈α
and␈α∞I␈α
was␈α∞in␈α
the␈α∞computer␈α
room␈α∞exercising␈α
LISP
␈↓ ↓H␈↓and␈α∞speaking␈α∂into␈α∞a␈α∞microphone.␈α∂ The␈α∞problem␈α∞chosen␈α∂was␈α∞to␈α∞determine␈α∂whether␈α∞a␈α∂first␈α∞order
␈↓ ↓H␈↓differential␈α
equation␈α
of␈α
the␈α
form␈α␈↓↓Mdx + Ndy␈↓␈α
was␈α
exact␈α
by␈α
testing␈α
whether␈α␈↓↓∂M/∂y = ∂N/∂x␈↓,␈α
which
␈↓ ↓H␈↓also involved some primitive algebraic simplification.

␈↓ ↓H␈↓␈↓ α_Everything␈α
was␈α
going␈α
well,␈α
if␈α
slowly,␈α
when␈α
suddenly␈α
the␈α
Flexowriter␈α
began␈α
to␈α
type␈α∞(at␈α
ten
␈↓ ↓H␈↓characters per second)

␈↓ ↓H␈↓"THE␈α GARBAGE␈α COLLECTOR␈α∨HAS␈α BEEN␈α CALLED.␈α   SOME␈α∨INTERESTING
␈↓ ↓H␈↓STATISTICS ARE AS FOLLOWS:"

␈↓ ↓H␈↓and␈α
on␈αand␈α
on␈α
and␈αon.␈α
 The␈α
garbage␈αcollector␈α
was␈αquite␈α
new␈α
at␈αthe␈α
time,␈α
we␈αwere␈α
rather␈αproud␈α
of
␈↓ ↓H␈↓it␈α∞and␈α∞curious␈α∞about␈α
it,␈α∞and␈α∞our␈α∞normal␈α∞output␈α
was␈α∞on␈α∞a␈α∞line␈α∞printer,␈α
so␈α∞it␈α∞printed␈α∞a␈α∞full␈α
page
␈↓ ↓H␈↓every␈αtime␈αit␈αwas␈αcalled␈αgiving␈αhow␈αmany␈αwords␈αwere␈αmarked␈αand␈αhow␈αmany␈αwere␈αcollected␈αand
␈↓ ↓H␈↓the size of list space, etc.

␈↓ ↓H␈↓␈↓ α_Nothing␈α∩had␈α∩ever␈α∩been␈α∩said␈α∩about␈α∩a␈α∩garbage␈α∩collector,␈α∩and␈α∩I␈α∩could␈α∩only␈α∩imagine␈α⊃the
␈↓ ↓H␈↓reaction␈α∂of␈α∂the␈α∂audience.␈α∂ We␈α∂were␈α∂already␈α⊂behind␈α∂time␈α∂on␈α∂a␈α∂tight␈α∂schedule,␈α∂it␈α∂was␈α⊂clear␈α∂that
␈↓ ↓H␈↓typing␈α∩out␈α⊃the␈α∩garbage␈α⊃collector␈α∩message␈α∩would␈α⊃take␈α∩all␈α⊃the␈α∩remaining␈α⊃time␈α∩allocated␈α∩to␈α⊃the
␈↓ ↓H␈↓demonstration, and both the lecturer and the audience were incapacitated by laughter.

␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓ARPANET: MCCARTHY@SU-AI

␈↓ ↓H␈↓␈↓εThis draft of LISP[F77,JMC] PUBbed at 18:26 on February 4, 1978.␈↓